#pragma once
#include<vector>
#include<map>
#include<memory>
#include<string>
namespace Trie
{
	class Node;
	using NodePtr = std::shared_ptr<Node>;
	class Node
	{
	public:
		Node():pass(0),end(0)
		{}
		int pass;
		int end;
		std::map<char,NodePtr>nexts;
	};

	class TrieTree
	{
	public:
		TrieTree():root(new Node())
		{
		}
		void AddWord(std::string str)
		{
			NodePtr node = root;
			for (size_t i = 0; i < str.size(); i++)
			{
				if (!node->nexts.count(str[i]))
				{
					node->nexts.insert(std::make_pair(str[i], NodePtr(new Node())));
				}
				node = node->nexts[str[i]];
				++node->pass;
				if (i == str.size() - 1)
				{
					++node->end;
					return;
				}
			}
		}
		int IsWordExist(std::string str)
		{
			NodePtr node = root;
			for (size_t i = 0; i < str.size(); i++)
			{    
				if (!node->nexts.count(str[i]))
				{
					return 0;
				}
				node = node->nexts[str[i]];
			}
			return node->end;
		}
		bool DeleteWord(std::string str)
		{
			if (!IsWordExist(str))
			{
				return false;
			}
			NodePtr node = root;
			for (size_t i = 0; i < str.size(); i++)
			{
				if (node->nexts[str[i]]->pass==1)
				{
					node->nexts.erase(str[i]);
					return false;
				}
				node = node->nexts[str[i]];
				--node->pass;
				if (i==str.size()-1)
				{
					--node->end;
					return true;
				}

			}
		}
		int PrefixWordNum(std::string str)
		{
			NodePtr node = root;

			for (size_t i = 0; i < str.size(); i++)
			{
				if (!node->nexts.count(str[i]))
				{
					return 0;
				}
				node = node->nexts[str[i]];
			}
			return node->pass;
		}

	private:
		NodePtr root;   
	};
	void test()
	{
		TrieTree tree;
		tree.AddWord("happy");
		tree.AddWord("love");
		tree.AddWord("gorgeous");
		tree.AddWord("baby");
		tree.AddWord("beautiful");
		tree.AddWord("cute");
		tree.AddWord("humble");
		tree.AddWord("lucky");
		tree.AddWord("China");
		tree.AddWord("love");
		tree.AddWord("baber");
		int num = tree.IsWordExist("love");
		tree.DeleteWord("love");
		num = tree.IsWordExist("love");
		tree.DeleteWord("love");
		num = tree.IsWordExist("love");
		num=tree.PrefixWordNum("ba");
	}
}